//简单选择排序
/*
    每一趟在待排序元素中选取关键字最小的元素加入有序子序列，且必须进行n-1趟排序
*/
/*
    不稳定
    时间复杂度O(n^2);
    空间复杂度O(1);
*/

#include <iostream>

using namespace std;

void SelectSort(int A[], int n) //简单选择排序(默认升序)
{
    for (int i = 0; i < n - 1; ++i) //共进行n-1躺排序
    {
        int min = i;  //记录最小元素的索引
        for (int j = i + 1; j < n;++j)  //在A[i……n-1]中选择最小的元素
            if (A[j] < A[min])          //更新最小元素的索引
                min = j;
        if (min != i)           //把最小元素放到前面已排好序序列的最后面
            swap(A[i], A[min]);
    }
    return;
}

//测试代码
int main()
{
    int A[100] = {2, 4, 3, 7, 9, 1, 6, 5, 8};
    SelectSort(A, 9);
    for (int i = 0; i < 9; ++i)
        cout << A[i] << ' ';
    return 0;
}